package offer.day19;

import java.util.ArrayList;
import java.util.Stack;

public class No32Third_PrintBinaryTreeByZ {
    /*面试题32：从上到下打印二叉树
     * 题目三：之字形打印二叉树
     * 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，
     * 第二行按照从右到左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
     * 例如：按之字形打印8->6   8->10 这样的二叉树，打印出8
     * 			  6->5   6->7			        10 6
     * 			  10->9  10->11			     5  7  9  11
     *
     * 思路1：按照这个规则，进行模拟一下，找其隐含的规律：
     *     循环：1>    将8输出，然后将8的子节点（左节点、右节点）6、10存入，（输出顺序10，6）；进出顺序符合栈的特性（先进后出）栈内：6 10
     * 		    2>    将10输出，然后将10的子节点（左节点、右节点）9、11存入 ， （输出顺序9、11）；进出顺序不符合栈的特性（先进先出）栈内：6 9 11
     *          3>    出错了，可以看出6，10，我们使用栈是对的，但是到了下一层就出了问题，若是改变入栈的顺序（右节点、左节点）11、9，（输出顺序9、11）那就正确了；栈内：6 11 9
     *          4>     但是现在仍旧不对，因为我们想要输出6，可是它被压在了栈底，这时，发现一个栈解决不了了，那我们再加一个栈，将二者分开根节点与子节点分开存放在两个栈中：看一下可不可行
     *          5>     从头开始：首先8输出，然后将8的子节点（左节点、右节点）6、10存入栈1，输出顺序10、6；栈1中  6 10      奇数层
     *          		       然后10输出，将 10的子节点（右节点、左节点）11、9存入栈2，输出顺序9、11；栈2中  11 9      偶数层
     *          		       然后6输出，将6的子节点（右节点、左节点）7、5存入栈2，输出顺序5、7；栈2中 11 9 7 5        偶数层
     *          		       这样输出正好是要的之字形顺序
     *  总结规律：
     *          输出节点，奇数层将子节点按照左、右的顺序进行存储；偶数层将子节点按照右、左的顺序进行存储。
     *  		输入输出就是遵循栈的特性先进后出
     *          将其看成是一个二维数组，将每一行存储到数组的每一行中，故设置一个二维的整型数组list;
     *          将stack1存储奇数层节点，stack2存储偶数层节点
     *          设置一个level记录到达了第几层,从第一层开始：
     *          只要两个栈有一个为非空战栈，则循环执行：
     *                          1>先判断是奇数层还是偶数层，
     *							2>若是奇数层，设置一个临时变量记录temp：每一层设置为一个一维整形数组存储每一行的数据
     *									栈1是存储奇数层的，所以处理栈1的数据，只要栈1不为空，
     *									就将栈顶节点弹出并记录进node（记录是为了后边要使用它的左节点和右节点，防止找不到），
     *									把弹出的节点node再放入到temp中，然后判断是否有左+右子树，如有压入是stack2中
     *									然后，再将temp中元素放入到list中，并且层数level+1，开始执行下一层的循环
     *						    3>若是偶数层，。。。与奇数层相似，这里不再赘述
     *
     * */
    public static void main(String[] args) {
        No32Third_PrintBinaryTreeByZ p=new No32Third_PrintBinaryTreeByZ();
        BinaryTreeNode root = new BinaryTreeNode(8);
        BinaryTreeNode one = new BinaryTreeNode(6);
        BinaryTreeNode two = new BinaryTreeNode(10);
        BinaryTreeNode three = new BinaryTreeNode(5);
        BinaryTreeNode four = new BinaryTreeNode(7);
        BinaryTreeNode five = new BinaryTreeNode(9);
        BinaryTreeNode six = new BinaryTreeNode(11);

        root.left = one;
        root.right = two;
        one.left = three;
        one.right = four;
        two.left = five;
        two.right = six;
        three.left = null;
        three.right = null;
        four.left = null;
        four.right = null;
        five.left = null;
        five.right = null;
        six.left = null;
        six.right = null;

        System.out.println("之字形打印二叉树");

        ArrayList<ArrayList<Integer>> list = p.PrintBinaryTreeByZWord(root);

        System.out.println(list);
    }

    private ArrayList<ArrayList<Integer>> PrintBinaryTreeByZWord(BinaryTreeNode root) {
        if(root==null) return new ArrayList<ArrayList<Integer>>();
        Stack<BinaryTreeNode> stack1=new Stack<>();
        Stack<BinaryTreeNode> stack2=new Stack<>();
        int level=1;
        stack1.push(root);
        ArrayList<ArrayList<Integer>> list=new ArrayList<>();
        while(!stack1.isEmpty() || !stack2.isEmpty()){
            ArrayList<Integer> tmp=new ArrayList<>();
            if(level%2==1){
                while(!stack1.isEmpty()){
                    BinaryTreeNode node=stack1.pop();
                    tmp.add(node.val);
                    if(node.left!=null){
                        stack2.push(node.left);
                    }
                    if(node.right!=null){
                        stack2.push(node.right);
                    }
                }

            }else{

                while(!stack2.isEmpty()){
                    BinaryTreeNode node=stack2.pop();
                    tmp.add(node.val);
                    if(node.right!=null){
                        stack1.push(node.right);
                    }
                    if(node.left!=null){
                        stack1.push(node.left);
                    }
                }
            }
            list.add(tmp);
            level++;
        }
        return list;
    }
}
